package com.mdnote.structure.stack;

import org.omg.CORBA.PRIVATE_MEMBER;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/24 0024
 * @description 中缀环后缀表达式
 */
public class InfixToPostfixExpression {


    // 表达式
    private String express;

    // 操作数字和符号的几何
    private List<String> items;

    public InfixToPostfixExpression(String express) {
        this.express = express;
        this.items = convert(express);
    }

    private List<String> convert(String express) {
        List<String> rtn = new ArrayList<>();

        int index = 0;
        do {
            if (express.charAt(index) >= 48 && express.charAt(index) <= 57) {
                // 如果是数字，|看看是不是多位数
                String tmp = "";
                while (index < express.length() && express.charAt(index) >= 48 && express.charAt(index) <= 57) {
                    tmp += express.substring(index, index + 1);
                    index ++;
                }
                rtn.add(tmp);
            } else {
                // 如果是符号，直接add
                rtn.add(express.substring(index, index + 1));
                index ++;
            }
        } while (index < express.length());

        return rtn;
    }

    public List<String> convertToPostfix() {
        // 创建一个栈，用于缓存符号
        Stack<Character> operationStack = new Stack<>();

        // 创建一个列表，用于保存后缀表达式
        List<String> postfixList = new ArrayList<>();

        // 遍历中缀表达式
        for (String item : this.items) {

            if (item.matches("\\d+")) {
                // 如果是数字，直接加入到列表中
                postfixList.add(item);
            } else if (item.equals("(")) {
                // 如果是左括号，直接入栈
                operationStack.push(item.charAt(0));
            } else if (item.equals(")")) {
                // 如果是右括号，一直pop元素直到遇到左括号为止，括号要丢掉
                while (!operationStack.isEmpty() && operationStack.peek() != '(') {
                    Character operation = operationStack.pop();
                    postfixList.add(String.valueOf(operation));
                }
                // 左括号要去掉
                if (!operationStack.isEmpty() && operationStack.peek() == '(') {
                    operationStack.pop();
                }
            } else if (item.charAt(0) < 48 || item.charAt(0) > 57) {
                // 如果是符号，判断栈是否为空
                if (operationStack.isEmpty() || operationStack.peek() == '(') {
                    // 如果为空或者栈顶为左括号，直接压栈
                    operationStack.push(item.charAt(0));
                } else {
                    // 否则，判断优先级
                    if (Operation.comparePriority(item.charAt(0), operationStack.peek())) {
                        // 如果优先级比栈顶高，直接加入列表
                        postfixList.add(item);
                    } else {
                        // 如果优先级比较低，弹出栈顶元素加入列表，直到优先级一样
                        while (!operationStack.isEmpty() && !Operation.comparePriority(item.charAt(0), operationStack.peek())) {
                            Character operation = operationStack.pop();
                            postfixList.add(String.valueOf(operation));
                        }
                        // 把自己加进去
                        operationStack.add(item.charAt(0));
                    }
                }
            }
        }
        // 最后把栈中的元素从栈顶开始加入列表
        while (!operationStack.isEmpty()) {
            postfixList.add(String.valueOf(operationStack.pop()));
        }

        return postfixList;
    }

    public static void main(String[] args) {
        InfixToPostfixExpression infixToPostfixExpression = new InfixToPostfixExpression("(3+7)*10-5");
        List<String> strings = infixToPostfixExpression.convertToPostfix();
        System.out.println(strings);
        PostfixExpressionCalc postfixExpressionCalc = new PostfixExpressionCalc(strings);
        System.out.println(postfixExpressionCalc.calculate());
    }
}
